import org.junit.jupiter.api.Test;
import tool.s;

import java.util.*;

public class S1add1 {

    List<List<Integer>> lists = new ArrayList<>(100);
    List<Integer> lista = new ArrayList<>(100);
    List<Integer> listb = new ArrayList<>(100);
    int sum = 0;
    Set<Integer> set = new HashSet<>();

    public List<List<Integer>> onePlusOne() {
        getState(101, 101);
//        for (int i = 0; i < lista.size(); i++) {
//            for (int j = 0; j < listb.size(); j++) {
//                if (lists.get(i).get(j) == -2) {
//                    getState(lista.get(i), listb.get(j));
//                }
//            }
//        }
//        System.out.println(lista.size() + " " + listb.size());
//        printList();
//        printWay(0, 101, 101);
        printKeyWay(0, 101, 101);
        return lists;
    }

    public int getState(int a, int b) {
        if (b / 100 == 10 && b % 100 == 10) return -1;
        if (lista.contains(a) && listb.contains(b)) {
            int res = lists.get(lista.indexOf(a)).get(listb.indexOf(b));
            if (res != -2) return res;
        } else {
            setList(a, b, -2);
        }
        List<Integer> next = getNext(a, b);
        boolean hasminus = false;
        boolean haszero = false;
        for (int i = 0; i < next.size(); i++) {
            int res = getState(b, next.get(i));
            if (res == -1) {
                setList(a, b, -1);
                hasminus = true;
            }
            if (res == 0) {
                haszero = true;
            }
        }
        int state = hasminus ? 1 : haszero ? 0 : -1;
        setList(a, b, state);
//        System.out.println(a + "  " + b + "->  " + state);
        return state;
    }

    public List<Integer> getNext(int a, int b) {
        List<Integer> next = new ArrayList<>(4);
        int[] as = {a / 100, a % 100};
        int[] bs = {b / 100, b % 100};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                if (as[i] == 10 || bs[j] == 10) continue;
                int tmp1 = as[0], tmp2 = as[1];
                as[i] = Math.min(as[i] + bs[j], 10);
                if (as[0] >= as[1]) as[0] = as[0] + as[1] - (as[1] = as[0]);
                next.add(as[0] * 100 + as[1]);
                as[0] = tmp1;
                as[1] = tmp2;
            }
        }
//        System.out.print(a + "  " + b + "->  ");
//        for (int i = 0; i < next.size(); i++) {
//            System.out.print(next.get(i) + ",  ");
//        }
//        System.out.println();
        return next;
    }

    public void setList(int a, int b, int state) {
        if (!lista.contains(a)) {
            lista.add(a);
            lists.add(new ArrayList<>(100));
            List<Integer> tmp = lists.get(lista.indexOf(a));
            for (int i = 0; i < listb.size(); i++) {
                tmp.add(-2);
            }
        }
        if (!listb.contains(b)) {
            listb.add(b);
            for (List<Integer> list : lists) {
                list.add(-2);
            }
        }
        lists.get(lista.indexOf(a)).set(listb.indexOf(b), state);
    }

    public void printList() {
        System.out.print(String.format("% 5d", 0));
        for (int i = 0; i < listb.size(); i++) {
            System.out.print(String.format("% 5d", listb.get(i)));
        }
        System.out.println();
        for (int i = 0; i < lista.size(); i++) {
            System.out.print(String.format("% 5d", lista.get(i)));
            for (int j = 0; j < listb.size(); j++) {
                System.out.print(String.format("% 5d", lists.get(i).get(j)));

            }
            System.out.println();
        }
    }

    public void printWay(int n, int a, int b) {
        if (!set.add(a * 1000 + b)) {
            return;
        }
        for (int i = 0; i < n; i++) {
            System.out.print("      ");
        }
        if (n % 2 == 0) {
            System.out.println(n + " " + a + "," + b + "->");
        } else {
            System.out.println(n + " " + b + "," + a + "->");
        }

        sum += 1;
        List<Integer> next = getNext(a, b);
        for (int i = 0; i < next.size(); i++) {
            if (n % 2 == 1 && getState(b, next.get(i)) != -1) {
                continue;
            }
            printWay(n + 1, b, next.get(i));
        }
    }

    public void printKeyWay(int n, int a, int b) {
        if (!set.add(a * 1000 + b)) {
            return;
        }
        List<Integer> next = getNext(a, b);
        int sum1 = 0;
        for (int i = 0; i < next.size(); i++) {
            if (n % 2 == 1 && getState(b, next.get(i)) == -1) {
                sum1++;
            }
        }
        if (sum1 == next.size()) return;
        boolean boo = false;
        for (int i = 0; i < next.size(); i++) {
            if (n % 2 == 1) {
                if (!boo && getState(b, next.get(i)) == -1 && next.get(i) != 1010) {
                    System.out.println(sum + " " + b + "," + a + "->" + b + "," + next.get(i));
                    sum++;
                    boo = true;
                } else {
                    continue;
                }
            }
            printKeyWay(n + 1, b, next.get(i));
        }
    }


    @Test
    public void test() {
        onePlusOne();
//        s.print(getNext(410,510));
//        getNext(410, 510);
    }

}
